// 前序遍历

// 输入: [1,null,2,3]
//    1
//     \
//      2
//     /
//    3
// 输出: [1, null, 2, 3]

import {Tree} from "./base-tree.js"

let t =new Tree();
t.insert(1);
t.insert(null);
t.insert(2);
t.insert(3);
console.log(t);

// 递归算法
let recursionPreorderTraversal  = function(root,array =[]){
    if(root){
        array.push(root.data)
        recursionPreorderTraversal(root.left,array )
        recursionPreorderTraversal(root.right,array )
    }
    return array 
}
console.log(recursionPreorderTraversal(t.root));

// 迭代算法
let iteratePreorderTraversal = function(root){
    const result = []
    const stack = []
    let current = root
    while (current || stack.length > 0){
        while (current){
            result.push(current.data)
            stack.push(current)
            current = current.left
        }
        current = stack.pop();
        current = current.right;
    }
    return result;
}
console.log(iteratePreorderTraversal(t.root));